package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _26环形链表II
 * @description
 * @date 2023/06/10 10:23
 * <p>
 * ******************************************************
 */
public class _26环形链表II {

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        // 是否有环
        boolean flag = false;

        // 走完该循环，就知有没有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                flag = true;
                break;
            }
        }

        if (flag) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

        return null;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
